{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Binary Tree Pruning"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: pruneTree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #二叉树剪枝"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你二叉树的根结点&nbsp;<code>root</code>&nbsp;，此外树的每个结点的值要么是 <code>0</code> ，要么是 <code>1</code> 。</p>\n",
    "\n",
    "<p>返回移除了所有不包含 <code>1</code> 的子树的原二叉树。</p>\n",
    "\n",
    "<p>节点 <code>node</code> 的子树为 <code>node</code> 本身加上所有 <code>node</code> 的后代。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://s3-lc-upload.s3.amazonaws.com/uploads/2018/04/06/1028_2.png\" style=\"width: 500px; height: 140px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,null,0,0,1]\n",
    "<strong>输出：</strong>[1,null,0,null,1]\n",
    "<strong>解释：</strong>\n",
    "只有红色节点满足条件“所有不包含 1 的子树”。 右图为返回的答案。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://s3-lc-upload.s3.amazonaws.com/uploads/2018/04/06/1028_1.png\" style=\"width: 500px; height: 115px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,0,1,0,0,0,1]\n",
    "<strong>输出：</strong>[1,null,1,null,1]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "<img alt=\"\" src=\"https://s3-lc-upload.s3.amazonaws.com/uploads/2018/04/05/1028.png\" style=\"width: 500px; height: 134px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,1,0,1,1,0,1,0]\n",
    "<strong>输出：</strong>[1,1,0,1,1,null,1]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树中节点的数目在范围 <code>[1, 200]</code> 内</li>\n",
    "\t<li><code>Node.val</code> 为 <code>0</code> 或 <code>1</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [binary-tree-pruning](https://leetcode.cn/problems/binary-tree-pruning/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [binary-tree-pruning](https://leetcode.cn/problems/binary-tree-pruning/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,null,0,0,1]', '[1,0,1,0,0,0,1]', '[1,1,0,1,1,0,1,0]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if root is None:\n",
    "            return None\n",
    "        root.left = self.pruneTree(root.left)\n",
    "        root.right = self.pruneTree(root.right)\n",
    "        if root.left is None and root.right is None and root.val == 0:\n",
    "            return None\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if root==None: return None\n",
    "        root.left=self.pruneTree(root.left)\n",
    "        root.right=self.pruneTree(root.right)\n",
    "        if root.left==None and root.right==None and root.val==0:\n",
    "            return None\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if root is None:\n",
    "            return None\n",
    "        root.left=self.pruneTree(root.left)\n",
    "        root.right=self.pruneTree(root.right)\n",
    "        if root.left==None and root.right==None and root.val==0:\n",
    "            return None\n",
    "        else:\n",
    "            return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree1(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "\n",
    "        def process(node):\n",
    "            if node is None:\n",
    "                return None\n",
    "\n",
    "            node.left = process(node.left)\n",
    "            node.right = process(node.right)\n",
    "\n",
    "            if node.left is None and node.right is None and node.val == 0:\n",
    "                return None\n",
    "            \n",
    "            return node\n",
    "        \n",
    "        return process(root)\n",
    "    \n",
    "    def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "\n",
    "        if root is None:\n",
    "            return None\n",
    "            \n",
    "        root.left = self.pruneTree(root.left)\n",
    "        root.right = self.pruneTree(root.right)\n",
    "\n",
    "        if root.left is None and root.right is None and root.val == 0:\n",
    "            return None\n",
    "        \n",
    "        return root\n",
    "    \n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return None\n",
    "        root.left = self.pruneTree(root.left)\n",
    "        root.right = self.pruneTree(root.right)\n",
    "        if root.val or root.left or root.right:\n",
    "            return root\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if root is None:\n",
    "            return None\n",
    "\n",
    "        root.left = self.pruneTree(root.left)\n",
    "        root.right = self.pruneTree(root.right)\n",
    "        if root.left is None and root.right is None and root.val == 0:\n",
    "            return None\n",
    "        \n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if not root:return \n",
    "        if not root.left and not root.right:\n",
    "            return root if root.val == 1 else None\n",
    "        root.left = self.pruneTree(root.left)\n",
    "        root.right = self.pruneTree(root.right)\n",
    "        if root.val == 1 or (root.left or root.right):\n",
    "            return root\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return root\n",
    "        root.left = self.pruneTree(root.left)\n",
    "        root.right = self.pruneTree(root.right)\n",
    "        if not root.left and not root.right and root.val == 0:\n",
    "            return None\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def process(self, head):\n",
    "        if not head:\n",
    "            return\n",
    "        elif head.val == 1:\n",
    "            self.flag = False\n",
    "            return \n",
    "\n",
    "        self.process(head.left)\n",
    "        if not self.flag:\n",
    "            return\n",
    "        self.process(head.right)\n",
    "\n",
    "    def pruneTree(self, root):\n",
    "        self.flag = True\n",
    "        queue = []\n",
    "\n",
    "        queue.append(root)\n",
    "\n",
    "        while queue:\n",
    "            node = queue.pop(0)\n",
    "            if not node:\n",
    "                continue\n",
    "\n",
    "            self.process(node.left)\n",
    "            if self.flag:\n",
    "                node.left = None\n",
    "            self.flag = True\n",
    "            self.process(node.right)\n",
    "            if self.flag:\n",
    "                node.right = None\n",
    "            self.flag = True\n",
    "\n",
    "            if node.left:\n",
    "                queue.append(node.left)\n",
    "            if node.right:\n",
    "                queue.append(node.right)\n",
    "\n",
    "        if (not root.left) and (not root.right):\n",
    "            if root.val == 0:\n",
    "                return None\n",
    "\n",
    "        return root\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if root is None:\n",
    "            return None\n",
    "        root.left=self.pruneTree(root.left)\n",
    "        root.right=self.pruneTree(root.right)\n",
    "        if root.left==None and root.right==None and root.val==0:\n",
    "            return None\n",
    "        return root\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return\n",
    "\n",
    "        root.left = self.pruneTree(root.left)\n",
    "        root.right = self.pruneTree(root.right)\n",
    "\n",
    "        if not root.left and not root.right and root.val == 0:\n",
    "            return\n",
    "        return root\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "\n",
    "        def prune(r):\n",
    "            if not r:return r\n",
    "            # if r.left:\n",
    "            r.left = prune(r.left)\n",
    "            # if r.right:\n",
    "            r.right = prune(r.right)\n",
    "            if r and r.val==0 and not r.left and not r.right:return None\n",
    "            return r\n",
    "\n",
    "        return prune(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        r = self.sumTree(root)\n",
    "        if r==0:\n",
    "            return None\n",
    "        else:\n",
    "            return root\n",
    "        \n",
    "    def sumTree(self, root):\n",
    "        left = 0\n",
    "        right = 0\n",
    "        if root.left is not None:\n",
    "            left = self.sumTree(root.left)\n",
    "            if left == 0:\n",
    "                root.left = None\n",
    "        if root.right is not None:\n",
    "            right = self.sumTree(root.right)\n",
    "            if right == 0:\n",
    "                root.right = None\n",
    "\n",
    "        return root.val+left+right\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        def containsOne(root):\n",
    "            if not root:\n",
    "                return False\n",
    "            left, right = containsOne(root.left), containsOne(root.right)\n",
    "            if not left:\n",
    "                root.left = None\n",
    "            if not right:\n",
    "                root.right = None\n",
    "            return root.val == 1 or left or right\n",
    "        flag = containsOne(root)\n",
    "        return None if not flag else root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "\n",
    "        if not root: return root\n",
    "        root.left = self.pruneTree(root.left)\n",
    "        root.right = self.pruneTree(root.right)\n",
    "        if root.left or root.right: return root\n",
    "        return None if root.val == 0 else root\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # if not root: return root\n",
    "        \n",
    "        # root.left = self.pruneTree(root.left)\n",
    "        # root.right = self.pruneTree(root.right)\n",
    "        \n",
    "        # if root.left or root.right:\n",
    "        #     return root\n",
    "        # return None if root.val == 0 else root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def process(self, head):\n",
    "        if not head:\n",
    "            return\n",
    "        elif head.val == 1:\n",
    "            self.flag = False\n",
    "            return \n",
    "\n",
    "        self.process(head.left)\n",
    "        if not self.flag:\n",
    "            return\n",
    "        self.process(head.right)\n",
    "\n",
    "    def pruneTree(self, root):\n",
    "        self.flag = True\n",
    "        queue = []\n",
    "\n",
    "        queue.append(root)\n",
    "\n",
    "        while queue:\n",
    "            node = queue.pop(0)\n",
    "            if not node:\n",
    "                continue\n",
    "\n",
    "            self.process(node.left)\n",
    "            if self.flag:\n",
    "                node.left = None\n",
    "            self.flag = True\n",
    "            self.process(node.right)\n",
    "            if self.flag:\n",
    "                node.right = None\n",
    "            self.flag = True\n",
    "\n",
    "            if node.left:\n",
    "                queue.append(node.left)\n",
    "            if node.right:\n",
    "                queue.append(node.right)\n",
    "\n",
    "        if (not root.left) and (not root.right):\n",
    "            if root.val == 0:\n",
    "                return None\n",
    "\n",
    "        return root\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if root is None:\n",
    "            return None\n",
    "        root.left = self.pruneTree(root.left)\n",
    "        root.right = self.pruneTree(root.right)\n",
    "        if not root.left and not root.right and root.val == 0:\n",
    "            return None\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 当遍历到一个结点时，如何判断该结点是否被释放：\n",
    "#           当该结点的左子树为空，右子树也为空，并且该结点为0时，会被释放。（函数体）\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return None\n",
    "        root.left = self.pruneTree(root.left)\n",
    "        root.right = self.pruneTree(root.right)\n",
    "        if root.val == 0 and not root.left and not root.right:\n",
    "            return None\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\r\n",
    "# class TreeNode:\r\n",
    "#     def __init__(self, val=0, left=None, right=None):\r\n",
    "#         self.val = val\r\n",
    "#         self.left = left\r\n",
    "#         self.right = right\r\n",
    "class Solution:\r\n",
    "    def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\r\n",
    "        if not root:\r\n",
    "            return None\r\n",
    "        root.left = self.pruneTree(root.left)\r\n",
    "        root.right = self.pruneTree(root.right)\r\n",
    "        if not root.left and not root.right and not root.val:\r\n",
    "            return None\r\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def dfs(self,root):\n",
    "        if root is None:\n",
    "            return None\n",
    "        \n",
    "        root.left = self.dfs(root.left)\n",
    "        root.right = self.dfs(root.right)\n",
    "\n",
    "        if root.left is None and root.right is None and root.val == 0:\n",
    "            return None\n",
    "        \n",
    "        return root\n",
    "    \n",
    "    def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "       res = TreeNode(-1)\n",
    "       res.left = root\n",
    "       self.dfs(res)\n",
    "       return res.left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return None\n",
    "        root.left = self.pruneTree(root.left)\n",
    "        root.right = self.pruneTree(root.right)\n",
    "        if root.val or root.left or root.right:\n",
    "            return root\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if root.left == None and root.right == None:\n",
    "            if root.val:\n",
    "                return root\n",
    "            return None\n",
    "        else:\n",
    "            if root.left:\n",
    "                root.left = self.pruneTree(root.left)\n",
    "            if root.right:\n",
    "                root.right = self.pruneTree(root.right)\n",
    "            if root.right != None or root.left != None or root.val:\n",
    "                return root\n",
    "            return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if not root: return None\n",
    "        root.left = self.pruneTree(root.left)\n",
    "        root.right = self.pruneTree(root.right)\n",
    "        if not root.left and not root.right and root.val == 0:\n",
    "            return None\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if not root:return None\n",
    "        root.left = self.pruneTree(root.left)\n",
    "        root.right = self.pruneTree(root.right)\n",
    "        if root.left is None and root.right is None and root.val == 0:\n",
    "            return None\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return None\n",
    "\n",
    "        # 修剪左右子树，并将修剪后的子树设置到对应位置\n",
    "        root.left = self.pruneTree(root.left)\n",
    "        root.right = self.pruneTree(root.right)\n",
    "        # 如果当前结点的值为 1 或者左/右子树存在，\n",
    "        # 则当前子树必定含有值为 1 的子结点，直接返回 root 即可\n",
    "        if root.val == 1 or root.left or root.right:\n",
    "            return root\n",
    "\n",
    "        # 此时当前子树中的所有子结点都是 0 ，需要修剪掉\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return None\n",
    "            \n",
    "            root.left = dfs(root.left)\n",
    "            root.right = dfs(root.right)\n",
    "\n",
    "            if root.val == 1 or root.left or root.right:\n",
    "                return root\n",
    "            else:\n",
    "                return None\n",
    "        return dfs(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return None\n",
    "        root.left = self.pruneTree(root.left)\n",
    "        root.right = self.pruneTree(root.right)\n",
    "        if root.left is None and root.right is None and root.val == 0:\n",
    "            return None\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if root==None:return None\n",
    "        l=self.pruneTree(root.left)\n",
    "        r=self.pruneTree(root.right)\n",
    "        if root.val==0 and l==None and r==None:return None\n",
    "        else:return TreeNode(root.val,l,r)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return None\n",
    "            root.left = dfs(root.left)\n",
    "            root.right = dfs(root.right)\n",
    "            if  root.left is None and  root.right is None and root.val == 0:\n",
    "                return None\n",
    "            return root\n",
    "        return dfs(root)\n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "\n",
    "        # def dfs(root):\n",
    "        if not root: return None\n",
    "        left = self.pruneTree(root.left)\n",
    "        right = self.pruneTree(root.right)\n",
    "        return None if not root.val and not left and not right else TreeNode(root.val, left, right)\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "\n",
    "        def dfs(node):\n",
    "            # True indicates no 1 included.\n",
    "            if not node:\n",
    "                return True\n",
    "\n",
    "            flag_left = dfs(node.left)\n",
    "            flag_right = dfs(node.right)\n",
    "\n",
    "            if flag_left :\n",
    "                node.left = None\n",
    "            if flag_right:\n",
    "                node.right = None\n",
    "                \n",
    "            return node.val == 0 and flag_left and flag_right\n",
    "\n",
    "        dummy = TreeNode(0, root, None)\n",
    "        dfs(dummy)\n",
    "        return dummy.left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "\n",
    "        def process(node):\n",
    "            if node is None:\n",
    "                return None\n",
    "                \n",
    "            node.left = process(node.left)\n",
    "            node.right = process(node.right)\n",
    "\n",
    "            if node.left is None and node.right is None and node.val == 0:\n",
    "                return None\n",
    "            \n",
    "            return node\n",
    "        \n",
    "        return process(root)\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        return self.traverse(root)\n",
    "\n",
    "    def traverse(self, root):\n",
    "        if not root:\n",
    "            return None\n",
    "        left = self.traverse(root.left)\n",
    "        right = self.traverse(root.right)\n",
    "        if root.val == 0 and left is None and right is None:\n",
    "            return None\n",
    "        root.left = left\n",
    "        root.right = right\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        dummy = TreeNode()\n",
    "        dummy.right = root\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return False\n",
    "            \n",
    "            l = dfs(root.left)\n",
    "            r = dfs(root.right)\n",
    "            if not l:\n",
    "                root.left = None\n",
    "            if not r:\n",
    "                root.right = None\n",
    "            if root.val == 1:\n",
    "                return True\n",
    "            return l or r \n",
    "        dfs(dummy)\n",
    "        return dummy.right\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return None\n",
    "        root.left = self.pruneTree(root.left)\n",
    "        root.right = self.pruneTree(root.right)\n",
    "        if root.val == 0 and not root.left and not root.right:\n",
    "            return None\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        \n",
    "        def dfs(node):#检测是否包含1\n",
    "            if not node:\n",
    "                return False\n",
    "            l = dfs(node.left)\n",
    "            if not l:\n",
    "                node.left = None\n",
    "            r = dfs(node.right)\n",
    "            if not r:\n",
    "                node.right = None\n",
    "            return l or r or node.val==1 #还需判断自身是否包含1\n",
    "        \n",
    "        if not dfs(root):\n",
    "            root = None\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        def dfs(root):\n",
    "            if not root: return None\n",
    "            root.left = dfs(root.left)\n",
    "            root.right = dfs(root.right)\n",
    "            if root.val == 1 or root.left or root.right: return root\n",
    "            else: return None\n",
    "        return dfs(root)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\r\n",
    "# class TreeNode:\r\n",
    "#     def __init__(self, val=0, left=None, right=None):\r\n",
    "#         self.val = val\r\n",
    "#         self.left = left\r\n",
    "#         self.right = right\r\n",
    "class Solution:\r\n",
    "    def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\r\n",
    "        if not root:\r\n",
    "            return None\r\n",
    "        root.left = self.pruneTree(root.left)\r\n",
    "        root.right = self.pruneTree(root.right)\r\n",
    "        if not root.left and not root.right and root.val == 0:\r\n",
    "            return None\r\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "\n",
    "        def dfs(x):\n",
    "            if x is None:\n",
    "                return None, True\n",
    "            \n",
    "            l, lf = dfs(x.left)\n",
    "            r, rf = dfs(x.right)\n",
    "\n",
    "            x.left = l\n",
    "            x.right = r\n",
    "\n",
    "            if lf and rf and x.val != 1:\n",
    "                return None, True\n",
    "            \n",
    "            return x, False\n",
    "        \n",
    "        ans, _ = dfs(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root):\n",
    "        if not root:\n",
    "            return None\n",
    "        root.left = self.pruneTree(root.left)\n",
    "        root.right = self.pruneTree(root.right)\n",
    "        if root.left is None and root.right is None and root.val == 0:\n",
    "            return None\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if not root: return\n",
    "        root.left = self.pruneTree(root.left)\n",
    "        root.right = self.pruneTree(root.right)\n",
    "        if not root.left and not root.right and root.val == 0:\n",
    "            return\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return False\n",
    "            if dfs(root.left) == False:\n",
    "                root.left = None\n",
    "            if dfs(root.right) == False:\n",
    "                root.right = None\n",
    "            return root.val == 1 or dfs(root.left) or dfs(root.right)\n",
    "        temp = TreeNode(1)\n",
    "        temp.left = root\n",
    "        dfs(temp)\n",
    "        return temp.left\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        #后序遍历\n",
    "        def validDfs(root):\n",
    "            if not root:\n",
    "                return -1\n",
    "            left = validDfs(root.left)\n",
    "            right = validDfs(root.right)\n",
    "            if left == 0:\n",
    "                root.left = None\n",
    "            if right == 0:\n",
    "                root.right = None\n",
    "            if left == -1 and right == -1:\n",
    "                return root.val\n",
    "            elif left == -1:\n",
    "                return right or root.val\n",
    "            elif right == -1:\n",
    "                return left or root.val\n",
    "            return left or right or root.val\n",
    "            \n",
    "        res = validDfs(root)\n",
    "        if res == 0 or res == -1:\n",
    "            return None\n",
    "        else:\n",
    "            return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if root is None:\n",
    "            return root\n",
    "        root.left = self.pruneTree(root.left)\n",
    "        root.right = self.pruneTree(root.right)\n",
    "        if root.val == 1 or root.left or root.right:\n",
    "            return root\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        root_sum = self.help(root)\n",
    "        return root if root_sum != 0 else None \n",
    "        pass\n",
    "\n",
    "    def help(self, node):\n",
    "        if node is None:\n",
    "            return 0\n",
    "\n",
    "        left_sum = self.help(node.left)\n",
    "        right_sum = self.help(node.right)\n",
    "        if left_sum==0:\n",
    "            node.left = None\n",
    "        if right_sum==0:\n",
    "            node.right = None\n",
    "        return left_sum + right_sum + node.val\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return\n",
    "        \n",
    "        root.left = self.pruneTree(root.left)\n",
    "        root.right = self.pruneTree(root.right)\n",
    "\n",
    "        if not root.left and not root.right:\n",
    "            if root.val == 0:\n",
    "                return\n",
    "        \n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "#  思路\n",
    "#  目的是剪掉所有全是0的分枝，\n",
    "#  可以递归看子树是否都为0，如果子树都为0即节点置为空; 子树都为空且自身是0就代表该节点可以被剪掉，返回空；\n",
    "#  否则返回递归剪枝后的左子树和右子树构成的新树。\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return None\n",
    "        left, right = self.pruneTree(root.left), self.pruneTree(root.right)\n",
    "        return None if not root.val and not left and not right else TreeNode(root.val, left,right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        #后序遍历\n",
    "        #注意如何整理逻辑，使之更清晰和简洁\n",
    "        #-1：节点为空 0:可以被剪枝 1：不可被剪枝\n",
    "        def validDfs(root):\n",
    "            if not root:\n",
    "                return -1\n",
    "            left = validDfs(root.left)\n",
    "            right = validDfs(root.right)\n",
    "            if left == 0:\n",
    "                root.left = None\n",
    "            if right == 0:\n",
    "                root.right = None\n",
    "            if left == -1 and right == -1:\n",
    "                return root.val\n",
    "            elif left == -1:\n",
    "                return right or root.val\n",
    "            elif right == -1:\n",
    "                return left or root.val\n",
    "            return left or right or root.val\n",
    "            \n",
    "        res = validDfs(root)\n",
    "        if res == 0 or res == -1:\n",
    "            return None\n",
    "        else:\n",
    "            return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return None\n",
    "\n",
    "        root.left = self.pruneTree(root.left)\n",
    "        root.right = self.pruneTree(root.right)\n",
    "        if root.val == 0 and not root.left and not root.right:\n",
    "            return None\n",
    "        return root "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if root is None:\n",
    "            return None\n",
    "\n",
    "        root.left = self.pruneTree(root.left)\n",
    "        root.right = self.pruneTree(root.right)\n",
    "\n",
    "        if root.left is None and root.right is None and root.val == 0:\n",
    "            return None\n",
    "        \n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        #后序遍历\n",
    "        def validDfs(root):\n",
    "            if not root:\n",
    "                return -1\n",
    "            left = validDfs(root.left)\n",
    "            right = validDfs(root.right)\n",
    "            if left == 0:\n",
    "                root.left = None\n",
    "            if right == 0:\n",
    "                root.right = None\n",
    "            if left == -1 and right == -1:\n",
    "                return root.val\n",
    "            elif left == -1:\n",
    "                return right or root.val\n",
    "            elif right == -1:\n",
    "                return left or root.val\n",
    "            return left or right or root.val\n",
    "            \n",
    "        res = validDfs(root)\n",
    "        if res == 0 or res == -1:\n",
    "            return None\n",
    "        else:\n",
    "            return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\"\"\"\n",
    "首先，无论要对树做什么处理，遍历是少不了的，而树的遍历基本都可以用DFS或BFS做，我用了DFS遍历\n",
    "进入dfs方法，dfs用于判断当前树是否含1\n",
    "特判：如果节点node为空，说明当前树不含1，返回False\n",
    "进入左子树递归，如果左子树不存在含1节点，令node.left为空\n",
    "进入右子树递归，如果右子树不存在含1节点，令node.right为空\n",
    "只要当前节点值为1或者左子树存在或者右子树存在，都可以返回True，表示当前树含有1，可以保留；否则，返回False\n",
    "返回根节点root，当根节点及其子树都不包含1时返回空\n",
    "\n",
    "作者：郁郁雨\n",
    "链接：https://leetcode.cn/problems/binary-tree-pruning/solutions/719284/814-er-cha-shu-jian-zhi-dfs-zhi-jie-di-g-pt1w/\n",
    "来源：力扣（LeetCode）\n",
    "著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。\"\"\"\n",
    "class Solution:\n",
    "    def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        return root if self.dfs(root)  else None\n",
    "    def dfs(self, node):\n",
    "        if not node:\n",
    "            return False\n",
    "        if not self.dfs(node.left):\n",
    "            node.left = None\n",
    "        if not self.dfs(node.right):\n",
    "            node.right = None\n",
    "        return node.val == 1 or node.left or node.right\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if root is None:\n",
    "            return None\n",
    "        root.left = self.pruneTree(root.left)\n",
    "        root.right = self.pruneTree(root.right)\n",
    "        if root.left is None and root.right is None and root.val == 0:\n",
    "            return None\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        root.left = self.pruneTree(root.left) if root.left else None\n",
    "        root.right = self.pruneTree(root.right) if root.right else None\n",
    "        if root.left is None and root.right is None and root.val == 0:\n",
    "            return None\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        def has_one(node):\n",
    "            if not node:\n",
    "                return False\n",
    "            if node.val == 0 and not has_one(node.left) and not has_one(node.right):\n",
    "                return False\n",
    "            return True\n",
    "        def pruning(node):\n",
    "            if not node:\n",
    "                return None\n",
    "            if not has_one(node.left):\n",
    "                node.left = None\n",
    "            else:\n",
    "                pruning(node.left)\n",
    "            if not has_one(node.right):\n",
    "                node.right = None\n",
    "            else:\n",
    "                pruning(node.right)\n",
    "            \n",
    "            if node.val == 0 and not node.left and not node.right:\n",
    "                return None\n",
    "            else:\n",
    "                return node\n",
    "        \n",
    "        return pruning(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: TreeNode) -> TreeNode:\n",
    "        if not root:\n",
    "            return None\n",
    "        root.left = self.pruneTree(root.left)\n",
    "        root.right = self.pruneTree(root.right)\n",
    "        if not root.val and not root.left and not root.right:\n",
    "            return None\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        def dfs(root):\n",
    "            if root is None:\n",
    "                return None\n",
    "            root.left = dfs(root.left)\n",
    "            root.right = dfs(root.right)\n",
    "            if root.val == 0 and root.left is None and root.right is None:\n",
    "                return None\n",
    "            return root\n",
    "        return dfs(root)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        # base case\n",
    "        if root is None:\n",
    "            return None\n",
    "        \n",
    "        if root.left:\n",
    "            root.left = self.pruneTree(root.left)\n",
    "        if root.right:\n",
    "            root.right = self.pruneTree(root.right)\n",
    "        # 如果当前节点值为0，并且左右子树为空，返回空 \n",
    "        if root.val == 0 and root.left is None and root.right is None:\n",
    "            return None\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        #边界情况\n",
    "        if root == None:\n",
    "            return\n",
    "        #方便用的判断叶节点的函数 \n",
    "        def leaf(x):\n",
    "            if x.left == None and x.right == None:\n",
    "                return True\n",
    "            return False\n",
    "        #对叶节点的情况处理\n",
    "        if leaf(root):\n",
    "            if root.val == 1:\n",
    "                return root\n",
    "            return\n",
    "        #找0函数\n",
    "        def findzero(x):\n",
    "            if x == None:\n",
    "                return False\n",
    "            if leaf(x): \n",
    "                if x.val == 0:\n",
    "                    return True\n",
    "                return False\n",
    "            return max(findzero(x.left),findzero(x.right))\n",
    "        #有0就操作一次\n",
    "        while findzero(root.left) == 1:\n",
    "            root.left = self.pruneTree(root.left)\n",
    "        while findzero(root.right) == 1:\n",
    "            root.right = self.pruneTree(root.right)\n",
    "        #最后根节点为0，两边变none的情况\n",
    "        if leaf(root):\n",
    "            if root.val == 1:\n",
    "                return root\n",
    "            return\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        def contain_one(node):\n",
    "            if not node:\n",
    "                return False\n",
    "            left = contain_one(node.left)\n",
    "            right = contain_one(node.right)\n",
    "            if not left:\n",
    "                node.left = None\n",
    "            if not right:\n",
    "                node.right = None\n",
    "            return node.val == 1 or node.left or node.right\n",
    "        \n",
    "        if not contain_one(root):\n",
    "            return None\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if root is None:\n",
    "            return None\n",
    "        root.left = self.pruneTree(root.left)\n",
    "        root.right = self.pruneTree(root.right)\n",
    "        if root.left is None and root.right is None and root.val == 0:\n",
    "            return None\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\r\n",
    "# class TreeNode:\r\n",
    "#     def __init__(self, val=0, left=None, right=None):\r\n",
    "#         self.val = val\r\n",
    "#         self.left = left\r\n",
    "#         self.right = right\r\n",
    "class Solution:\r\n",
    "    def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\r\n",
    "        if not root:\r\n",
    "            return None\r\n",
    "        root.left=self.pruneTree(root.left)\r\n",
    "        root.right=self.pruneTree(root.right)\r\n",
    "        if not root.left and not root.right and root.val==0:\r\n",
    "            return None\r\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return None\n",
    "        \n",
    "        root.left = self.pruneTree(root.left)\n",
    "        root.right = self.pruneTree(root.right)\n",
    "\n",
    "        if root.val == 0 and not root.left and not root.right:\n",
    "            return None\n",
    "        \n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if root is None:\n",
    "            return None\n",
    "        \n",
    "        dummy_root = TreeNode(left=root)\n",
    "        \n",
    "        def traverse(root) -> bool:\n",
    "            if root is None:\n",
    "                return False\n",
    "            \n",
    "            left_has_one = traverse(root.left)\n",
    "            right_has_one = traverse(root.right)\n",
    "            if not left_has_one:\n",
    "                root.left = None\n",
    "            if not right_has_one:\n",
    "                root.right = None\n",
    "\n",
    "            if not left_has_one and not right_has_one and root.val != 1:\n",
    "                return False\n",
    "            else:\n",
    "                return True\n",
    "\n",
    "        traverse(dummy_root)\n",
    "        return dummy_root.left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def process(self, head):\n",
    "        if not head:\n",
    "            return\n",
    "        elif head.val == 1:\n",
    "            self.flag = False\n",
    "            return \n",
    "\n",
    "        self.process(head.left)\n",
    "        if not self.flag:\n",
    "            return\n",
    "        self.process(head.right)\n",
    "\n",
    "    def pruneTree(self, root):\n",
    "        self.flag = True\n",
    "        queue = []\n",
    "\n",
    "        queue.append(root)\n",
    "\n",
    "        while queue:\n",
    "            node = queue.pop(0)\n",
    "            if not node:\n",
    "                continue\n",
    "\n",
    "            self.process(node.left)\n",
    "            if self.flag:\n",
    "                node.left = None\n",
    "            self.flag = True\n",
    "            self.process(node.right)\n",
    "            if self.flag:\n",
    "                node.right = None\n",
    "            self.flag = True\n",
    "\n",
    "            if node.left:\n",
    "                queue.append(node.left)\n",
    "            if node.right:\n",
    "                queue.append(node.right)\n",
    "\n",
    "        if (not root.left) and (not root.right):\n",
    "            if root.val == 0:\n",
    "                return None\n",
    "\n",
    "        return root\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        def dep_first(node):\n",
    "            if node:\n",
    "                if node.left and dep_first(node.left):\n",
    "                    node.left = None\n",
    "                if node.right and dep_first(node.right):\n",
    "                    node.right = None\n",
    "\n",
    "                if node.left == None and node.right == None and node.val == 0:\n",
    "                    return True\n",
    "                return False\n",
    "\n",
    "        if dep_first(root):\n",
    "            return None\n",
    "        return root\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        return self.traverse(root)\n",
    "\n",
    "    def traverse(self, root):\n",
    "        if not root:\n",
    "            return None\n",
    "        left = self.traverse(root.left)\n",
    "        right = self.traverse(root.right)\n",
    "        if root.val == 0 and left is None and right is None:\n",
    "            return None\n",
    "        root.left = left\n",
    "        root.right = right\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "class Solution:\n",
    "    def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return None \n",
    "            node.left = dfs(node.left)\n",
    "            node.right = dfs(node.right)\n",
    "            if node.val == 0 and not node.left and not node.right:\n",
    "                return None \n",
    "            return node \n",
    "        \n",
    "        return dfs(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: Optional[TreeNode]):\n",
    "        if not root:\n",
    "            return None\n",
    "        left, right = self.pruneTree(root.left), self.pruneTree(root.right)\n",
    "        return None if not root.val and not left and not right else TreeNode(root.val, left, right)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
